﻿using System;
using System.Collections.Generic;
using System.Linq;

namespace NekoVampire.Extension
{
    static class IEnumerableExt
    {
        public static IEnumerable<TSource> QuickSort<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IComparer<TKey> comparer)
        {
            /*
            int count = source.Count();
            if (count <= 1) return source;
            int point = count / 2;

            comparer = comparer ?? Comparer<TKey>.Default;

            TSource p = source.ElementAt(point);
            var xs = source.Take(point).Concat(source.Skip(point + 1));
            var lo = xs.Where(y => comparer.Compare(keySelector(y), keySelector(p)) < 0);
            var hi = xs.Where(y => comparer.Compare(keySelector(y), keySelector(p)) >= 0);

            return lo.QuickSort(keySelector).Concat(new[] { p }).Concat(hi.QuickSort(keySelector));
             */
            var list = source.ToList();
            comparer = comparer ?? Comparer<TKey>.Default;
            list.Sort(new Comp<TSource, TKey>(keySelector, comparer));
            return list;
        }

        public static IEnumerable<TSource> QuickSort<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector)
        {
            return source.QuickSort(keySelector, null);
        }

        public static IEnumerable<TSource> QuickSort<TSource>(this IEnumerable<TSource> source)
        {
            return source.QuickSort(null);
        }

        public static IEnumerable<TSource> QuickSort<TSource>(this IEnumerable<TSource> source, IComparer<TSource> comparer)
        {
            var list = source.ToList();
            comparer = comparer ?? Comparer<TSource>.Default;
            list.Sort(comparer);
            return list;
        }

        private class Comp<TSource, TKey> : IComparer<TSource>
        {
            Func<TSource, TKey> keySelector;
            IComparer<TKey> comparer;

            public Comp (Func<TSource, TKey> keySelector, IComparer<TKey> comparer)
            {
                this.keySelector = keySelector;
                this.comparer = comparer;
            }

            public int Compare(TSource x, TSource y)
            {
                return comparer.Compare(keySelector(x), keySelector(y));
            }
        }
    }
}
